﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0211_MissingTwo : IAlgorithm
    {
        // 面试题 17.19. 消失的两个数字

        /*
        给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
        以任意顺序返回这两个数字均可。

        提示：
            nums.length <= 30000
        */

        public void Test()
        {
            var res = MissingTwo(new int[] { });
            foreach (var item in res)
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        public int[] MissingTwo(int[] nums)
        {
            int xorsum = 0;
            int n = nums.Length + 2;
            foreach (int num in nums) xorsum ^= num;
            for (int i = 1; i <= n; i++) xorsum ^= i;
            // 防止溢出
            int lsb = (xorsum == int.MinValue ? xorsum : xorsum & (-xorsum));
            int type1 = 0, type2 = 0;
            foreach (int num in nums)
                if ((num & lsb) != 0) type1 ^= num;
                else type2 ^= num;
            for (int i = 1; i <= n; i++)
                if ((i & lsb) != 0) type1 ^= i;
                else type2 ^= i;
            return new int[] { type1, type2 };
        }
    }
}
